package leetcode.editor.cn;

import java.util.*;

public class _399_EvaluateDivision {
    public static void main(String[] args) {
        Solution solution = new _399_EvaluateDivision().new Solution();
        List<String> e1 = new LinkedList<String>(Arrays.asList("a", "b"));
        List<String> e2 = new LinkedList<String>(Arrays.asList("b", "c"));
        List<List<String>> equations = new LinkedList<>(Arrays.asList(e1, e2));
        double[] values = {2.0, 3.0};
        List<String> q1 = new LinkedList<String>(Arrays.asList("a", "c"));
        List<String> q2 = new LinkedList<String>(Arrays.asList("b", "a"));
        List<String> q3 = new LinkedList<String>(Arrays.asList("a", "e"));
        List<String> q4 = new LinkedList<String>(Arrays.asList("a", "a"));
        List<String> q5 = new LinkedList<String>(Arrays.asList("x", "x"));
        List<List<String>> querys = new LinkedList<>(Arrays.asList(q1, q2, q3, q4, q5));
        double[] doubles = solution.calcEquation(equations, values, querys);
        System.out.println(Arrays.toString(doubles));
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    class Node {
        // 邻接节点代表的字符串
        public String id;
        // 到达邻接节点所需的倍数
        public double num;

        public Node(String i, double n) {
            id = i;
            num = n;
        }
    }


    // 广度优先搜索
    class Solution {
        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
            int n = equations.size();
            Map<String, List<Node>> map = new HashMap<>();
            double[] ret = new double[queries.size()];
            for (int i = 0; i < n; i++) {
                String dividend = equations.get(i).get(0), divisor = equations.get(i).get(1);
                if (!map.containsKey(dividend)) {
                    map.put(dividend, new ArrayList<>());
                }
                if (!map.containsKey(divisor)) {
                    map.put(divisor, new ArrayList<>());
                }
                map.get(dividend).add(new Node(divisor, values[i]));
                map.get(divisor).add(new Node(dividend, 1.0 / values[i]));
            }

            int cnt = 0;
            for (List<String> query : queries) {
                if (map.containsKey(query.get(0)) && map.containsKey(query.get(1))) {
                    String cur = query.get(0), dest = query.get(1);
                    Map<String, Double> ratios = new HashMap<>();
                    ratios.put(cur, 1.0);
                    Set<String> set = new HashSet<>();
                    Queue<String> queue = new LinkedList<>();

                    queue.add(cur);
                    while (!queue.isEmpty() && !set.contains(dest)) {
                        String u = queue.remove();
                        set.add(u);
                        for (Node node : map.get(u)) {
                            if (!set.contains(node.id)) {
                                ratios.put(node.id, ratios.get(u) * node.num);
                                queue.add(node.id);
                                if (node.id.equals(dest)) {
                                    break;
                                }
                            }
                        }
                    }
                    ret[cnt++] = ratios.getOrDefault(dest, -1.0);
                } else {
                    ret[cnt++] = -1.0;
                }
            }
            return ret;
        }
    }


    // 深度优先搜索
    class Solution2 {
        Map<String, List<Node>> map;

        /**
         * 计算 cur 到 dest 的倍率
         *
         * @param cur   当前顶点
         * @param dest  目标顶点
         * @param ratio 当前倍率
         * @param set   已经记录了的顶点集合
         * @return 当前顶点到目标顶点的倍率
         */
        private double dfs(String cur, String dest, double ratio, Set<String> set) {
            if (cur.equals(dest)) {
                return ratio;
            }
            set.add(cur);
            for (Node node : map.get(cur)) {
                if (!set.contains(node.id)) {
                    double temp = dfs(node.id, dest, ratio * node.num, set);
                    if (temp != -1) {
                        return temp;
                    }
                }
            }
            return -1.0;
        }

        public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
            int n = equations.size();
            map = new HashMap<>();
            double[] ret = new double[queries.size()];

            for (int i = 0; i < n; i++) {
                String dividend = equations.get(i).get(0);
                String divisor = equations.get(i).get(1);

                if (!map.containsKey(dividend)) {
                    map.put(dividend, new ArrayList<>());
                }
                if (!map.containsKey(divisor)) {
                    map.put(divisor, new ArrayList<>());
                }

                map.get(dividend).add(new Node(divisor, values[i]));
                map.get(divisor).add(new Node(dividend, 1.0 / values[i]));
            }

            int cnt = 0;
            for (List<String> query : queries) {
                if (map.containsKey(query.get(0)) && map.containsKey(query.get(1))) {
                    ret[cnt++] = dfs(query.get(0), query.get(1), 1.0, new HashSet<>());
                } else {
                    ret[cnt++] = -1.0;
                }
            }
            return ret;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
// 定义邻接节点类


}